<!DOCTYPE html>
<html lang="zh_cn">
<head>
          <title>来玩魔王的咚</title>
        <meta name="viewport" content="width=device-width, initial-scale=1" />
        <meta charset="utf-8" />
        <!-- twitter card metadata -->
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="/images/mowang.png">
<meta name="twitter:site" content="">
<meta name="twitter:title" content="Go程序基础">
<meta name="twitter:description" content="<p>Go中的名称：关键字，内置预声明，命名规则；基础数据类型：整数操作符，布尔运算符，布尔转数值；字符串和字节切片：bytes包；复合数据类型：切片的反转、平移、比较，map使用切片、用作集合；位向量集合：计算置位个数，自适应32或64位平台</p>">
        <!-- OG Tags -->
<meta property="og:url" content="/gopl-basic-knowledge.html"/>
<meta property="og:title" content="来玩魔王的咚 | Go程序基础" />
<meta property="og:description" content="<p>Go中的名称：关键字，内置预声明，命名规则；基础数据类型：整数操作符，布尔运算符，布尔转数值；字符串和字节切片：bytes包；复合数据类型：切片的反转、平移、比较，map使用切片、用作集合；位向量集合：计算置位个数，自适应32或64位平台</p>" />
        <!-- favicon -->
        <link rel="icon" type="image/png" href="/images/mowang.png">
        <!-- moment.js for date formatting -->
        <script src="/theme/js/moment.js"></script>
        <!-- css -->
        <link rel="stylesheet" type="text/css" href="/theme/css/main.css" />
        <!-- 左边的menu，如果页面高度不够，就跟着滚动，否则文章分类显示不全 -->
        <link rel="stylesheet" type="text/css" href="/theme/css/mycss/menu.css" />
		<script>
			
                /*! grunt-grunticon Stylesheet Loader - v2.1.2 | https://github.com/filamentgroup/grunticon | (c) 2015 Scott Jehl, Filament Group, Inc. | MIT license. */
    
    (function(e){function t(t,n,r,o){"use strict";function a(){for(var e,n=0;u.length>n;n++)u[n].href&&u[n].href.indexOf(t)>-1&&(e=!0);e?i.media=r||"all":setTimeout(a)}var i=e.document.createElement("link"),l=n||e.document.getElementsByTagName("script")[0],u=e.document.styleSheets;return i.rel="stylesheet",i.href=t,i.media="only x",i.onload=o||null,l.parentNode.insertBefore(i,l),a(),i}var n=function(r,o){"use strict";if(r&&3===r.length){var a=e.navigator,i=e.Image,l=!(!document.createElementNS||!document.createElementNS("http://www.w3.org/2000/svg","svg").createSVGRect||!document.implementation.hasFeature("http://www.w3.org/TR/SVG11/feature#Image","1.1")||e.opera&&-1===a.userAgent.indexOf("Chrome")||-1!==a.userAgent.indexOf("Series40")),u=new i;u.onerror=function(){n.method="png",n.href=r[2],t(r[2])},u.onload=function(){var e=1===u.width&&1===u.height,a=r[e&&l?0:e?1:2];n.method=e&&l?"svg":e?"datapng":"png",n.href=a,t(a,null,null,o)},u.src="",document.documentElement.className+=" grunticon"}};n.loadCSS=t,e.grunticon=n})(this);(function(e,t){"use strict";var n=t.document,r="grunticon:",o=function(e){if(n.attachEvent?"complete"===n.readyState:"loading"!==n.readyState)e();else{var t=!1;n.addEventListener("readystatechange",function(){t||(t=!0,e())},!1)}},a=function(e){return t.document.querySelector('link[href$="'+e+'"]')},c=function(e){var t,n,o,a,c,i,u={};if(t=e.sheet,!t)return u;n=t.cssRules?t.cssRules:t.rules;for(var l=0;n.length>l;l++)o=n[l].cssText,a=r+n[l].selectorText,c=o.split(");")[0].match(/US\-ASCII\,([^"']+)/),c&&c[1]&&(i=decodeURIComponent(c[1]),u[a]=i);return u},i=function(e){var t,o,a;o="data-grunticon-embed";for(var c in e)if(a=c.slice(r.length),t=n.querySelectorAll(a+"["+o+"]"),t.length)for(var i=0;t.length>i;i++)t[i].innerHTML=e[c],t[i].style.backgroundImage="none",t[i].removeAttribute(o);return t},u=function(t){"svg"===e.method&&o(function(){i(c(a(e.href))),"function"==typeof t&&t()})};e.embedIcons=i,e.getCSS=a,e.getIcons=c,e.ready=o,e.svgLoadedCallback=u,e.embedSVG=u})(grunticon,this);
                
                grunticon(["/theme/css/icons.data.svg.css", "/theme/css/icons.data.png.css", "/theme/css/icons.fallback.css"]);
            </script>
        <noscript><link href="/theme/css/icons.fallback.css" rel="stylesheet"></noscript>
        <!-- menu toggle javascript -->
        <script type="text/javascript">
            document.addEventListener("DOMContentLoaded", initMenu);
            
            function initMenu(){
                var menu = document.getElementById("menu");
                var menulink = document.getElementById("menu-link");
                menulink.addEventListener("click", function toggleMenu(){
                        window.event.preventDefault();
                        menulink.classList.toggle('active');
                        menu.classList.toggle('active');              
                    });
            };
        </script>
        <!-- 不蒜子 -->
        <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>

    <meta name="description" content="<p>Go中的名称：关键字，内置预声明，命名规则；基础数据类型：整数操作符，布尔运算符，布尔转数值；字符串和字节切片：bytes包；复合数据类型：切片的反转、平移、比较，map使用切片、用作集合；位向量集合：计算置位个数，自适应32或64位平台</p>" />

    <meta name="tags" content="gopl" />
  <!-- 替换部分base的样式，看文章时，要再宽一点，右边有很多空间可以撑开 -->
  <link rel="stylesheet" type="text/css" href="/theme/css/mycss/article.css" />

</head>
<body>
    <div role="banner" id="masthead">
        <header>
            <a href="/"><img src="/images/mowang.png" alt="McManus Logo"></a>
                <h1>来玩魔王的咚@骑士救兵</h1>
            <a href="#menu" id="menu-link">more stuff</a>
            <nav id="menu">
                <ul>
                        <li><a href="/tags">tags</a></li>
                            <li><a href="/category/cloud.html">Cloud</a></li>
                            <li><a href="/category/docker.html">Docker</a></li>
                            <li class="active"><a href="/category/go.html">Go</a></li>
                            <li><a href="/category/linux.html">Linux</a></li>
                            <li><a href="/category/python.html">Python</a></li>
                            <li><a href="/category/xue-xi-bi-ji.html">学习笔记</a></li>
                            <li><a href="/category/yun-wei-zi-dong-hua.html">运维自动化</a></li>
                </ul>
            </nav>
        </header>
    </div>
        <div class="page" role="main">
  <div class="article" role="article">
    <article>
        <footer>
            <a name="top"></a>
            <p>
              <time datetime=" 2020-07-13 14:30:00+08:00">
                <script>document.write(moment('2020-07-13 14:30:00+08:00').format('LL'));</script>
              </time>
              ~
              <time datetime=" 2020-07-13 14:30:00+08:00">
                <script>document.write(moment('2020-07-13 14:30:00+08:00').format('LL'));</script>
              </time>
            </p>
        </footer>
        <header>
          <h2>
            Go程序基础
          </h2>
        </header>
      <div class="content">
         <div class="toc">
<ul>
<li><a href="#go-zhong-de-ming-cheng">Go 中的名称</a><ul>
<li><a href="#guan-jian-zi">关键字</a></li>
<li><a href="#nei-zhi-yu-sheng-ming">内置预声明</a></li>
<li><a href="#ming-ming-gui-ze">命名规则</a></li>
</ul>
</li>
<li><a href="#ji-chu-shu-ju-lei-xing">基础数据类型</a><ul>
<li><a href="#zheng-shu">整数</a></li>
<li><a href="#bu-er-zhi">布尔值</a></li>
<li><a href="#zi-fu-chuan-he-zi-jie-qie-pian-bytes-bao">字符串和字节切片（bytes包）</a></li>
</ul>
</li>
<li><a href="#fu-he-shu-ju-lei-xing">复合数据类型</a><ul>
<li><a href="#qie-pian-slice">切片（slice）</a></li>
<li><a href="#map">map</a></li>
</ul>
</li>
<li><a href="#wei-xiang-liang-ji-he">位向量集合</a><ul>
<li><a href="#ji-chu-lei-xing-he-fang-fa">基础类型和方法</a></li>
<li><a href="#bing-ji-jiao-ji-cha-ji-dui-chen-cha">并集、交集、差集、对称差</a></li>
<li><a href="#ji-suan-zhi-wei-ge-shu">计算置位个数</a></li>
<li><a href="#tian-jia-qi-ta-fang-fa">添加其他方法</a></li>
<li><a href="#zi-shi-ying-32-huo-64-wei-ping-tai">自适应32或64位平台</a></li>
</ul>
</li>
</ul>
</div>
<h3 id="go-zhong-de-ming-cheng"><a class="toclink" href="#go-zhong-de-ming-cheng">Go 中的名称</a></h3>
<p>Go 中函数、变量、常量、类型、语句标签和包的名称遵循一个简单的规则：名称的开头是一个字母（Unicode 中的字符即可）或下划线，后面可以跟任意数量的字符、数字和下划线，并区分大小写。  </p>
<h4 id="guan-jian-zi"><a class="toclink" href="#guan-jian-zi">关键字</a></h4>
<p>共25个关键字，只能用在语法允许的地方，不能作为名称：</p>
<div class="highlight"><pre><span></span><code>break       //退出循环
default     //选择结构默认项（switch、select）
func        //定义函数
interface   //定义接口
select      //channel
case        //选择结构标签
chan        //定义channel
const       //常量
continue    //跳过本次循环
defer       //延迟执行内容（收尾工作）
go          //并发执行
map         //map类型
struct      //定义结构体
else        //选择结构
goto        //跳转语句
package     //包
switch      //选择结构
fallthrough //switch里继续检查后面的分支
if          //选择结构
range       //从slice、map等结构中取元素
type        //定义类型
for         //循环
import      //导入包
return      //返回
var         //定义变量
</code></pre></div>

<h4 id="nei-zhi-yu-sheng-ming"><a class="toclink" href="#nei-zhi-yu-sheng-ming">内置预声明</a></h4>
<p>内置的预声明的常量、类型和函数：</p>
<ul>
<li>常量</li>
<li>true、false</li>
<li>iota</li>
<li>nil</li>
<li>类型</li>
<li>int、int8、int16、int32、int64</li>
<li>uint、uint8、uint16、uint32、uint64、uintptr</li>
<li>float32、float64、complex128、complex64</li>
<li>bool、byte、rune、string、error</li>
<li>函数</li>
<li>make、len、cap、new、append、copy、close、delete</li>
<li>complex、real、imag ： 复数相关</li>
<li>panic、recover</li>
</ul>
<p>这些名称不是预留的，可以在声明中使用它们。也可能会看到对其中的名称进行重声明，但是要知道这会有冲突的风险。  </p>
<h4 id="ming-ming-gui-ze"><a class="toclink" href="#ming-ming-gui-ze">命名规则</a></h4>
<p>单词组合时，使用驼峰式。如果是缩写，比如：ASCII或HTML，要么全大写，要么全小写。<br>
比如组合 html 和 escape，可以是下面几种写法：
+ htmlEscape
+ HTMLEscape
+ EscapeHTML</p>
<p>但是不推荐这样的写法：</p>
<ul>
<li>Escapehtml : 这样完全区分不了html是一个词，所以这样HTML要全大写</li>
<li>EscapeHtml : 这样虽然能区分，但是违反了全大写或全小写的建议</li>
</ul>
<h3 id="ji-chu-shu-ju-lei-xing"><a class="toclink" href="#ji-chu-shu-ju-lei-xing">基础数据类型</a></h3>
<p>Go的数据类型分四大类：</p>
<ol>
<li>基础类型（basic type）<ul>
<li>数字（number）</li>
<li>字符串（string）</li>
<li>布尔型（boolean）</li>
</ul>
</li>
<li>聚合类型（aggregate type）<ul>
<li>数组（array）</li>
<li>结构体（struct）</li>
</ul>
</li>
<li>引用类型（reference type）<ul>
<li>指针（pointer）</li>
<li>切片（slice）</li>
<li>散列表（map）</li>
<li>函数（function）</li>
<li>通道（channel）</li>
</ul>
</li>
<li>接口类型（interface type）</li>
</ol>
<h4 id="zheng-shu"><a class="toclink" href="#zheng-shu">整数</a></h4>
<h5 id="er-yuan-cao-zuo-fu"><a class="toclink" href="#er-yuan-cao-zuo-fu">二元操作符</a></h5>
<p>二元操作符分五大优先级，按优先级降序排列：</p>
<div class="highlight"><pre><span></span><code>*    /   %   &lt;&lt;  &gt;&gt;  &amp;   &amp;^
+    -   |   ^
==    !=  &lt;   &lt;=  &gt;   &gt;=
&amp;&amp;
||
</code></pre></div>

<h5 id="wei-yun-suan-fu"><a class="toclink" href="#wei-yun-suan-fu">位运算符</a></h5>
<p>位运算符：</p>
<table>
<thead>
<tr>
<th>符号</th>
<th>说明</th>
<th>集合</th>
</tr>
</thead>
<tbody>
<tr>
<td>&amp;</td>
<td>AND</td>
<td>交集</td>
</tr>
<tr>
<td>|</td>
<td>OR</td>
<td>并集</td>
</tr>
<tr>
<td>^</td>
<td>XOR</td>
<td>对称差</td>
</tr>
<tr>
<td>&amp;^</td>
<td>位清空（AND NOT）</td>
<td>差集</td>
</tr>
<tr>
<td>&lt;&lt;</td>
<td>左移</td>
<td>N/A</td>
</tr>
<tr>
<td>&gt;&gt;</td>
<td>右移</td>
<td>N/A</td>
</tr>
</tbody>
</table>
<p>位清空，表达式 z=x&amp;^y ，把y中是1的位在x里对应的那个位，置0。<br>
差集，就是集合x去掉集合y中的元素之后的集合。对称差则是再加上集合y去掉集合x中的元素的集合，就是前后两个集合互相求差集，之后再并集。  </p>
<h4 id="bu-er-zhi"><a class="toclink" href="#bu-er-zhi">布尔值</a></h4>
<h5 id="luo-ji-yun-suan-fu"><a class="toclink" href="#luo-ji-yun-suan-fu">逻辑运算符</a></h5>
<p>逻辑运算符 &amp;&amp;(AND) 以及 ||(OR) 的运算可能引起<strong>短路行为</strong>：如果运算符左边的操作数已经能够直接确定总体结果，则右边的操作数不会做计算。<br>
关于<strong>优先级</strong>，&amp;&amp; 较 || 优先级更高，这里有一个方便记忆的窍门。&amp;&amp; 表示逻辑乘法，|| 表示逻辑加法，这不仅仅指优先级，计算结果也很相似。  </p>
<h5 id="bu-er-zhuan-shu-zhi"><a class="toclink" href="#bu-er-zhuan-shu-zhi">布尔转数值</a></h5>
<p>布尔值无法隐式转换成数值，反之也不行。如果需要把布尔值转成0或1，需要显示的使用if：</p>
<div class="highlight"><pre><span></span><code><span class="nx">i</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="mi">0</span><span class="w"></span>
<span class="k">if</span><span class="w"> </span><span class="nx">b</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="nx">i</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">1</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>

<p>如果转换操作使用频繁，值得专门写成一个函数：</p>
<div class="highlight"><pre><span></span><code><span class="kd">func</span><span class="w"> </span><span class="nx">btoi</span><span class="p">(</span><span class="nx">b</span><span class="w"> </span><span class="kt">bool</span><span class="p">)</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="k">if</span><span class="w"> </span><span class="nx">b</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="k">return</span><span class="w"> </span><span class="mi">1</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="mi">0</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="kd">func</span><span class="w"> </span><span class="nx">itob</span><span class="p">(</span><span class="nx">i</span><span class="w"> </span><span class="kt">int</span><span class="p">)</span><span class="w"> </span><span class="kt">bool</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="nx">i</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="mi">0</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>

<p>反向转换比较简单，所以无需专门写成函数了。不过为了与btoi对应，上面也写了一个。  </p>
<h4 id="zi-fu-chuan-he-zi-jie-qie-pian-bytes-bao"><a class="toclink" href="#zi-fu-chuan-he-zi-jie-qie-pian-bytes-bao">字符串和字节切片（bytes包）</a></h4>
<p>字节切片 []byte 类型，其某些属性和字符串相同。但是由于字符串不可变，因此按增量方式构建字符串会导致多次内存分配和复制。这种情况下，使用 bytes.Buffer 类型更高效。<br>
bytes 包为高效处理字节切片提供了 Buffer 类型。Buffer 初始值为空，其大小随着各种类型数据的写入而增长，如 string、byte 和 []byte。bytes.Buffer 变量无须初始化，其零值有意义：</p>
<div class="highlight"><pre><span></span><code><span class="kn">package</span><span class="w"> </span><span class="nx">main</span><span class="w"></span>

<span class="kn">import</span><span class="w"> </span><span class="p">(</span><span class="w"></span>
<span class="w">    </span><span class="s">&quot;bytes&quot;</span><span class="w"></span>
<span class="w">    </span><span class="s">&quot;fmt&quot;</span><span class="w"></span>
<span class="p">)</span><span class="w"></span>

<span class="c1">// 函数 intsToString 与 fmt.Sprintf(values) 类似，但插入了逗号</span><span class="w"></span>
<span class="kd">func</span><span class="w"> </span><span class="nx">intsToString</span><span class="p">(</span><span class="nx">values</span><span class="w"> </span><span class="p">[]</span><span class="kt">int</span><span class="p">)</span><span class="w"> </span><span class="kt">string</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="kd">var</span><span class="w"> </span><span class="nx">buf</span><span class="w"> </span><span class="nx">bytes</span><span class="p">.</span><span class="nx">Buffer</span><span class="w"></span>
<span class="w">    </span><span class="nx">buf</span><span class="p">.</span><span class="nx">WriteByte</span><span class="p">(</span><span class="sc">&#39;[&#39;</span><span class="p">)</span><span class="w"></span>
<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="nx">i</span><span class="p">,</span><span class="w"> </span><span class="nx">v</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="k">range</span><span class="w"> </span><span class="nx">values</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="k">if</span><span class="w"> </span><span class="nx">i</span><span class="w"> </span><span class="p">&gt;</span><span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="nx">buf</span><span class="p">.</span><span class="nx">WriteString</span><span class="p">(</span><span class="s">&quot;, &quot;</span><span class="p">)</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"></span>
<span class="w">        </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Fprintf</span><span class="p">(</span><span class="o">&amp;</span><span class="nx">buf</span><span class="p">,</span><span class="w"> </span><span class="s">&quot;%d&quot;</span><span class="p">,</span><span class="w"> </span><span class="nx">v</span><span class="p">)</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="nx">buf</span><span class="p">.</span><span class="nx">WriteByte</span><span class="p">(</span><span class="sc">&#39;]&#39;</span><span class="p">)</span><span class="w"></span>
<span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="nx">buf</span><span class="p">.</span><span class="nx">String</span><span class="p">()</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="kd">func</span><span class="w"> </span><span class="nx">main</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Println</span><span class="p">(</span><span class="nx">intsToString</span><span class="p">([]</span><span class="kt">int</span><span class="p">{</span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="mi">2</span><span class="p">,</span><span class="w"> </span><span class="mi">3</span><span class="p">}))</span><span class="w">  </span><span class="c1">// &quot;[1, 2, 3]&quot;</span><span class="w"></span>
<span class="w">    </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Println</span><span class="p">([]</span><span class="kt">int</span><span class="p">{</span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="mi">2</span><span class="p">,</span><span class="w"> </span><span class="mi">3</span><span class="p">})</span><span class="w">  </span><span class="c1">// &quot;[1 2 3]&quot;</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>

<h3 id="fu-he-shu-ju-lei-xing"><a class="toclink" href="#fu-he-shu-ju-lei-xing">复合数据类型</a></h3>
<p>有四种复合数据类型：</p>
<ul>
<li>数组</li>
<li>切片（slice）</li>
<li>map</li>
<li>结构体</li>
</ul>
<h4 id="qie-pian-slice"><a class="toclink" href="#qie-pian-slice">切片（slice）</a></h4>
<h5 id="fan-zhuan-he-ping-yi"><a class="toclink" href="#fan-zhuan-he-ping-yi">反转和平移</a></h5>
<p>就地反转slice中的元素：</p>
<div class="highlight"><pre><span></span><code><span class="kn">package</span><span class="w"> </span><span class="nx">main</span><span class="w"></span>

<span class="kn">import</span><span class="w"> </span><span class="s">&quot;fmt&quot;</span><span class="w"></span>

<span class="kd">func</span><span class="w"> </span><span class="nx">reverse</span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="p">[]</span><span class="kt">int</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="nx">i</span><span class="p">,</span><span class="w"> </span><span class="nx">j</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="mi">0</span><span class="p">,</span><span class="w"> </span><span class="nb">len</span><span class="p">(</span><span class="nx">s</span><span class="p">)</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span><span class="w"> </span><span class="nx">i</span><span class="w"> </span><span class="p">&lt;</span><span class="w"> </span><span class="nx">j</span><span class="p">;</span><span class="w"> </span><span class="nx">i</span><span class="p">,</span><span class="w"> </span><span class="nx">j</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nx">i</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="nx">j</span><span class="o">-</span><span class="mi">1</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="nx">s</span><span class="p">[</span><span class="nx">i</span><span class="p">],</span><span class="w"> </span><span class="nx">s</span><span class="p">[</span><span class="nx">j</span><span class="p">]</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nx">s</span><span class="p">[</span><span class="nx">j</span><span class="p">],</span><span class="w"> </span><span class="nx">s</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="kd">func</span><span class="w"> </span><span class="nx">main</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="nx">l</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="p">[</span><span class="o">...</span><span class="p">]</span><span class="kt">int</span><span class="p">{</span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="mi">2</span><span class="p">,</span><span class="w"> </span><span class="mi">3</span><span class="p">,</span><span class="w"> </span><span class="mi">4</span><span class="p">,</span><span class="w"> </span><span class="mi">5</span><span class="p">}</span><span class="w"> </span><span class="c1">// 这个是数组</span><span class="w"></span>
<span class="w">    </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Println</span><span class="p">(</span><span class="nx">l</span><span class="p">)</span><span class="w"></span>
<span class="w">    </span><span class="nx">reverse</span><span class="p">(</span><span class="nx">l</span><span class="p">[:])</span><span class="w"> </span><span class="c1">// 传入切片</span><span class="w"></span>
<span class="w">    </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Println</span><span class="p">(</span><span class="nx">l</span><span class="p">)</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>

<p>将一个切片向左平移n个元素的简单方法是连续调用三次反转函数。第一次反转前n个元素，第二次返回剩下的元素，最后整体做一次反转：</p>
<div class="highlight"><pre><span></span><code><span class="kd">func</span><span class="w"> </span><span class="nx">moveLeft</span><span class="p">(</span><span class="nx">n</span><span class="w"> </span><span class="kt">int</span><span class="p">,</span><span class="w"> </span><span class="nx">s</span><span class="w"> </span><span class="p">[]</span><span class="kt">int</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="nx">reverse</span><span class="p">(</span><span class="nx">s</span><span class="p">[:</span><span class="nx">n</span><span class="p">])</span><span class="w"></span>
<span class="w">    </span><span class="nx">reverse</span><span class="p">(</span><span class="nx">s</span><span class="p">[</span><span class="nx">n</span><span class="p">:])</span><span class="w"></span>
<span class="w">    </span><span class="nx">reverse</span><span class="p">(</span><span class="nx">s</span><span class="p">)</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="kd">func</span><span class="w"> </span><span class="nx">moveRight</span><span class="p">(</span><span class="nx">n</span><span class="w"> </span><span class="kt">int</span><span class="p">,</span><span class="w"> </span><span class="nx">s</span><span class="w"> </span><span class="p">[]</span><span class="kt">int</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="nx">reverse</span><span class="p">(</span><span class="nx">s</span><span class="p">[</span><span class="nx">n</span><span class="p">:])</span><span class="w"></span>
<span class="w">    </span><span class="nx">reverse</span><span class="p">(</span><span class="nx">s</span><span class="p">[:</span><span class="nx">n</span><span class="p">])</span><span class="w"></span>
<span class="w">    </span><span class="nx">reverse</span><span class="p">(</span><span class="nx">s</span><span class="p">)</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>

<h5 id="qie-pian-de-bi-jiao"><a class="toclink" href="#qie-pian-de-bi-jiao">切片的比较</a></h5>
<p>与数组不同，切片无法做比较。标准库中提供了高度优化的函数 bytes.Equal 来比较两个字节切片（[]byte）。但是对其他类型的切片，Go不支持比较。<br>
当然自己写一个比较的函数也不难：</p>
<div class="highlight"><pre><span></span><code><span class="kd">func</span><span class="w"> </span><span class="nx">equal</span><span class="p">(</span><span class="nx">x</span><span class="p">,</span><span class="w"> </span><span class="nx">y</span><span class="w"> </span><span class="p">[]</span><span class="kt">string</span><span class="p">)</span><span class="w"> </span><span class="kt">bool</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="k">if</span><span class="w"> </span><span class="nb">len</span><span class="p">(</span><span class="nx">x</span><span class="p">)</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="nb">len</span><span class="p">(</span><span class="nx">y</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="k">return</span><span class="w"> </span><span class="kc">false</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="nx">i</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="k">range</span><span class="w"> </span><span class="nx">x</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="k">if</span><span class="w"> </span><span class="nx">x</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="nx">y</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="k">return</span><span class="w"> </span><span class="kc">false</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="kc">true</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>

<p>上面的方法也只是返回执行函数当时的结果，但是切片的底层数组可以能发生改变，在不同的时间切片所拥有的元素可能不同，不能保证整个生命周期都保持不变。总之，Go不允许直接比较切片。  </p>
<h5 id="chu-shi-hua"><a class="toclink" href="#chu-shi-hua">初始化</a></h5>
<p>像切片和map这类引用类型，使用前是需要初始化的。仅仅进行声明，是不分配内存的，此时值为nil。<br>
完成初始化后（大括号或者make函数），此时就是已经完成了初始化，分配内存空间，值不为nil。  </p>
<h5 id="he-nil-bi-jiao"><a class="toclink" href="#he-nil-bi-jiao">和nil比较</a></h5>
<p>切片唯一允许的比较操作是和nil做比较。值为nil的切片长度和容量都是零，但是也有非nil的切片长度和容量也都是零的：</p>
<div class="highlight"><pre><span></span><code><span class="kd">func</span><span class="w"> </span><span class="nx">main</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="kd">var</span><span class="w"> </span><span class="nx">s</span><span class="w"> </span><span class="p">[]</span><span class="kt">int</span><span class="w"></span>
<span class="w">    </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Println</span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="kc">nil</span><span class="p">)</span><span class="w">  </span><span class="c1">// true</span><span class="w"></span>
<span class="w">    </span><span class="nx">s</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="kc">nil</span><span class="w"></span>
<span class="w">    </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Println</span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="kc">nil</span><span class="p">)</span><span class="w">  </span><span class="c1">// true</span><span class="w"></span>
<span class="w">    </span><span class="nx">s</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">[]</span><span class="nb">int</span><span class="p">(</span><span class="kc">nil</span><span class="p">)</span><span class="w"></span>
<span class="w">    </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Println</span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="kc">nil</span><span class="p">)</span><span class="w">  </span><span class="c1">// true</span><span class="w"></span>
<span class="w">    </span><span class="nx">s</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">[]</span><span class="kt">int</span><span class="p">{}</span><span class="w"></span>
<span class="w">    </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Println</span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="kc">nil</span><span class="p">)</span><span class="w">  </span><span class="c1">// flase</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>

<p>所以要检查一个切片是否为空，应该使用 len(s) == 0，而不是和nil做比较。<br>
另外，值为nil的切片其表现和其它长度为零的切片是一样的。无论值是否为nil，GO的函数都应该以相同的方式对待所有长度为零的切片。  </p>
<h4 id="map"><a class="toclink" href="#map">map</a></h4>
<h5 id="yin-yong-lei-xing"><a class="toclink" href="#yin-yong-lei-xing">引用类型</a></h5>
<p>因为map类型是间接的指向它的 key/value 对，所以函数或方法对引用本身做的任何改变，比如设置值为 nil 或者使它指向一个不同的 map，都不会在调用者身上产生作用：</p>
<div class="highlight"><pre><span></span><code><span class="kn">package</span><span class="w"> </span><span class="nx">main</span><span class="w"></span>

<span class="kn">import</span><span class="w"> </span><span class="s">&quot;fmt&quot;</span><span class="w"></span>

<span class="kd">type</span><span class="w"> </span><span class="nx">map1</span><span class="w"> </span><span class="kd">map</span><span class="p">[</span><span class="kt">string</span><span class="p">]</span><span class="kt">string</span><span class="w"></span>

<span class="kd">func</span><span class="w"> </span><span class="nx">change</span><span class="p">(</span><span class="nx">m</span><span class="w"> </span><span class="nx">map1</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Println</span><span class="p">(</span><span class="s">&quot;change:&quot;</span><span class="p">,</span><span class="w"> </span><span class="nx">m</span><span class="p">)</span><span class="w"> </span><span class="c1">// change: map[k1:v1]</span><span class="w"></span>
<span class="w">    </span><span class="nx">m</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nx">map1</span><span class="p">{</span><span class="s">&quot;k1&quot;</span><span class="p">:</span><span class="w"> </span><span class="s">&quot;v2&quot;</span><span class="p">}</span><span class="w"> </span><span class="c1">// 将m指向一个新的map，但是并不会改变main中m1的值</span><span class="w"></span>
<span class="w">    </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Println</span><span class="p">(</span><span class="s">&quot;change:&quot;</span><span class="p">,</span><span class="w"> </span><span class="nx">m</span><span class="p">)</span><span class="w"> </span><span class="c1">// change: map[k1:v2]</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="kd">func</span><span class="w"> </span><span class="nx">main</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="nx">m1</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">map1</span><span class="p">{</span><span class="s">&quot;k1&quot;</span><span class="p">:</span><span class="w"> </span><span class="s">&quot;v1&quot;</span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Println</span><span class="p">(</span><span class="s">&quot;main:&quot;</span><span class="p">,</span><span class="w"> </span><span class="nx">m1</span><span class="p">)</span><span class="w"> </span><span class="c1">// main: map[k1:v1]</span><span class="w"></span>
<span class="w">    </span><span class="nx">change</span><span class="p">(</span><span class="nx">m1</span><span class="p">)</span><span class="w"> </span><span class="c1">// m1 的值不会改变</span><span class="w"></span>
<span class="w">    </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Println</span><span class="p">(</span><span class="s">&quot;main&quot;</span><span class="p">,</span><span class="w"> </span><span class="nx">m1</span><span class="p">)</span><span class="w"> </span><span class="c1">// main map[k1:v1]</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>

<p>main函数中创建了m1，然后把m1传递给change函数，引用类型传的是存储了m1的内存地址的副本。在change中修改m的值，指向了一个新创建的map，此时m就指向了新创建的map的内存地址。回到main函数中m1指向的内存地址并没有改变，而该地址对应的map的内容也没有改变。  </p>
<p>下面这个函数，main函数中原来的map是会改变的。main函数中map的指向的地址没有变，但是地址对应的数据发生了变化：</p>
<div class="highlight"><pre><span></span><code><span class="kd">func</span><span class="w"> </span><span class="nx">changeKeyValue</span><span class="p">(</span><span class="nx">m</span><span class="w"> </span><span class="nx">map1</span><span class="p">,</span><span class="w"> </span><span class="nx">k</span><span class="p">,</span><span class="w"> </span><span class="nx">v</span><span class="w"> </span><span class="kt">string</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Println</span><span class="p">(</span><span class="s">&quot;change:&quot;</span><span class="p">,</span><span class="w"> </span><span class="nx">m</span><span class="p">)</span><span class="w"></span>
<span class="w">    </span><span class="nx">m</span><span class="p">[</span><span class="nx">k</span><span class="p">]</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nx">v</span><span class="w"></span>
<span class="w">    </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Println</span><span class="p">(</span><span class="s">&quot;change:&quot;</span><span class="p">,</span><span class="w"> </span><span class="nx">m</span><span class="p">)</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>

<h5 id="shi-yong-qie-pian-zuo-key"><a class="toclink" href="#shi-yong-qie-pian-zuo-key">使用切片做key</a></h5>
<p>切片是不能作为key的，并且切片是不可比较的，不过可以有一个间接的方法来实现切片作key。<br>
定义一个帮助函数k，将每一个key都映射到字符串：</p>
<div class="highlight"><pre><span></span><code><span class="kd">var</span><span class="w"> </span><span class="nx">m</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nb">make</span><span class="p">(</span><span class="kd">map</span><span class="p">[</span><span class="kt">string</span><span class="p">]</span><span class="kt">int</span><span class="p">)</span><span class="w"></span>

<span class="kd">func</span><span class="w"> </span><span class="nx">k</span><span class="p">(</span><span class="nx">list</span><span class="w"> </span><span class="p">[]</span><span class="kt">string</span><span class="p">)</span><span class="w"> </span><span class="kt">string</span><span class="w"> </span><span class="p">{</span><span class="w"> </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Sprint</span><span class="p">(</span><span class="s">&quot;%q&quot;</span><span class="p">,</span><span class="w"> </span><span class="nx">list</span><span class="p">)</span><span class="w"> </span><span class="p">}</span><span class="w"></span>

<span class="kd">func</span><span class="w"> </span><span class="nx">Add</span><span class="p">(</span><span class="nx">list</span><span class="w"> </span><span class="p">[]</span><span class="kt">string</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"> </span><span class="nx">m</span><span class="p">[</span><span class="nx">k</span><span class="p">(</span><span class="nx">list</span><span class="p">)]</span><span class="o">++</span><span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="kd">func</span><span class="w"> </span><span class="nx">Count</span><span class="p">(</span><span class="nx">list</span><span class="w"> </span><span class="p">[]</span><span class="kt">string</span><span class="p">)</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="p">{</span><span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="nx">m</span><span class="p">[</span><span class="nx">k</span><span class="p">(</span><span class="nx">list</span><span class="p">)]</span><span class="w"> </span><span class="p">}</span><span class="w"></span>
</code></pre></div>

<p>这里使用%q来格式化切片，就是包含双引号的字符串，所以（["ab", "cd"] 和 ["abcd"]）是不一样的。就是，当且仅当 x 和 y 相等的时候，才认为 k(x)==k(y)。<br>
同样的方法适用于任何不可直接比较的key类型，不仅仅局限于切片。同样，k(x) 的类型不一定是字符串类型，任何能够得到想要的比较结果的可比较类型都可以。  </p>
<h5 id="ji-he"><a class="toclink" href="#ji-he">集合</a></h5>
<p>Go 没有提供集合类型，但是利用key唯一的特点，可以用map来实现这个功能。<br>
比如说字符串的集合：</p>
<div class="highlight"><pre><span></span><code><span class="kn">package</span><span class="w"> </span><span class="nx">main</span><span class="w"></span>

<span class="kn">import</span><span class="w"> </span><span class="p">(</span><span class="w"></span>
<span class="w">    </span><span class="s">&quot;bufio&quot;</span><span class="w"></span>
<span class="w">    </span><span class="s">&quot;fmt&quot;</span><span class="w"></span>
<span class="w">    </span><span class="s">&quot;os&quot;</span><span class="w"></span>
<span class="p">)</span><span class="w"></span>

<span class="kd">func</span><span class="w"> </span><span class="nx">main</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="nx">seen</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nb">make</span><span class="p">(</span><span class="kd">map</span><span class="p">[</span><span class="kt">string</span><span class="p">]</span><span class="kt">bool</span><span class="p">)</span><span class="w"> </span><span class="c1">// 字符串集合</span><span class="w"></span>
<span class="w">    </span><span class="nx">input</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">bufio</span><span class="p">.</span><span class="nx">NewScanner</span><span class="p">(</span><span class="nx">os</span><span class="p">.</span><span class="nx">Stdin</span><span class="p">)</span><span class="w"></span>
<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="nx">input</span><span class="p">.</span><span class="nx">Scan</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="nx">line</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">input</span><span class="p">.</span><span class="nx">Text</span><span class="p">()</span><span class="w"></span>
<span class="w">        </span><span class="k">if</span><span class="w"> </span><span class="p">!</span><span class="nx">seen</span><span class="p">[</span><span class="nx">line</span><span class="p">]</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="nx">seen</span><span class="p">[</span><span class="nx">line</span><span class="p">]</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="kc">true</span><span class="w"></span>
<span class="w">            </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Println</span><span class="p">(</span><span class="s">&quot;Set:&quot;</span><span class="p">,</span><span class="w"> </span><span class="nx">line</span><span class="p">)</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="k">if</span><span class="w"> </span><span class="nx">err</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">input</span><span class="p">.</span><span class="nx">Err</span><span class="p">();</span><span class="w"> </span><span class="nx">err</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="kc">nil</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Fprintf</span><span class="p">(</span><span class="nx">os</span><span class="p">.</span><span class="nx">Stderr</span><span class="p">,</span><span class="w"> </span><span class="s">&quot;dedup: %v\n&quot;</span><span class="p">,</span><span class="w"> </span><span class="nx">err</span><span class="p">)</span><span class="w"></span>
<span class="w">        </span><span class="nx">os</span><span class="p">.</span><span class="nx">Exit</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>

<p>从标准输出获取字符串，用map来存储已经出现过的行，只有首次出现的字符串才会打印出来。  </p>
<p><strong>使用空结构体作value</strong><br>
上面的集合中使用bool来作为map的value，而bool也有true和false两种值，而实际只使用了1种值。<br>
这里还可以使用空结构体（类型：struct{}、值：struct{}{}）。空结构体，没有长度，也不携带任何信息，用它可能是最合适的。但由于这种方式节约的内存很少并且语法复杂，所以一般尽量避免这样使用。  </p>
<h3 id="wei-xiang-liang-ji-he"><a class="toclink" href="#wei-xiang-liang-ji-he">位向量集合</a></h3>
<p>Go 语言的集合通常使用 map[T]bool 来实现，其中T是元素类型。使用 map 的集合扩展性良好，但是对于一些特定的问题，一个专门设计过的集合性能会更优。比如，在数据流分析领域，集合元素都是小的非负整型，集合拥有许多元素，而且集合的操作多数是求并集和交集，<strong>位向量</strong>是个理想的数据结构。  </p>
<h4 id="ji-chu-lei-xing-he-fang-fa"><a class="toclink" href="#ji-chu-lei-xing-he-fang-fa">基础类型和方法</a></h4>
<p>位向量使用一个无符号整型值的切片，每一位代表集合中的一个元素。如果设置第 i 位的元素，则表示集合包含 i。下面是一个包含了三个方法的简单位向量类型：</p>
<div class="highlight"><pre><span></span><code><span class="kn">package</span><span class="w"> </span><span class="nx">intset</span><span class="w"></span>

<span class="kn">import</span><span class="w"> </span><span class="p">(</span><span class="w"></span>
<span class="w">    </span><span class="s">&quot;bytes&quot;</span><span class="w"></span>
<span class="w">    </span><span class="s">&quot;fmt&quot;</span><span class="w"></span>
<span class="p">)</span><span class="w"></span>

<span class="c1">// 这是一个包含非负整数的集合</span><span class="w"></span>
<span class="c1">// 零值代表空的集合</span><span class="w"></span>
<span class="kd">type</span><span class="w"> </span><span class="nx">IntSet</span><span class="w"> </span><span class="kd">struct</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="nx">words</span><span class="w"> </span><span class="p">[]</span><span class="kt">uint64</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="c1">// 集合中是否存在非负整数x</span><span class="w"></span>
<span class="kd">func</span><span class="w"> </span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="nx">Has</span><span class="p">(</span><span class="nx">x</span><span class="w"> </span><span class="kt">int</span><span class="p">)</span><span class="w"> </span><span class="kt">bool</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="nx">word</span><span class="p">,</span><span class="w"> </span><span class="nx">bit</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">x</span><span class="o">/</span><span class="mi">64</span><span class="p">,</span><span class="w"> </span><span class="nb">uint</span><span class="p">(</span><span class="nx">x</span><span class="o">%</span><span class="mi">64</span><span class="p">)</span><span class="w"></span>
<span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="nx">word</span><span class="w"> </span><span class="p">&lt;</span><span class="w"> </span><span class="nb">len</span><span class="p">(</span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">)</span><span class="w"> </span><span class="o">&amp;&amp;</span><span class="w"> </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">[</span><span class="nx">word</span><span class="p">]</span><span class="o">&amp;</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="nx">bit</span><span class="p">)</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="mi">0</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="c1">// 添加一个数x到集合中</span><span class="w"></span>
<span class="kd">func</span><span class="w"> </span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="nx">Add</span><span class="p">(</span><span class="nx">x</span><span class="w"> </span><span class="kt">int</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="nx">word</span><span class="p">,</span><span class="w"> </span><span class="nx">bit</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">x</span><span class="o">/</span><span class="mi">64</span><span class="p">,</span><span class="w"> </span><span class="nb">uint</span><span class="p">(</span><span class="nx">x</span><span class="o">%</span><span class="mi">64</span><span class="p">)</span><span class="w"></span>
<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="nx">word</span><span class="w"> </span><span class="o">&gt;=</span><span class="w"> </span><span class="nb">len</span><span class="p">(</span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nb">append</span><span class="p">(</span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">,</span><span class="w"> </span><span class="mi">0</span><span class="p">)</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">[</span><span class="nx">word</span><span class="p">]</span><span class="w"> </span><span class="o">|=</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="o">&lt;&lt;</span><span class="w"> </span><span class="nx">bit</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="c1">// 求并集，并保存到s中</span><span class="w"></span>
<span class="kd">func</span><span class="w"> </span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="nx">UnionWith</span><span class="p">(</span><span class="nx">t</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="nx">i</span><span class="p">,</span><span class="w"> </span><span class="nx">tword</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="k">range</span><span class="w"> </span><span class="nx">t</span><span class="p">.</span><span class="nx">words</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="k">if</span><span class="w"> </span><span class="nx">i</span><span class="w"> </span><span class="p">&lt;</span><span class="w"> </span><span class="nb">len</span><span class="p">(</span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="o">|=</span><span class="w"> </span><span class="nx">tword</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nb">append</span><span class="p">(</span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">,</span><span class="w"> </span><span class="nx">tword</span><span class="p">)</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="c1">// 以字符串&quot;{1 2 3}&quot;的形式返回集合</span><span class="w"></span>
<span class="kd">func</span><span class="w"> </span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="nx">String</span><span class="p">()</span><span class="w"> </span><span class="kt">string</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="kd">var</span><span class="w"> </span><span class="nx">buf</span><span class="w"> </span><span class="nx">bytes</span><span class="p">.</span><span class="nx">Buffer</span><span class="w"></span>
<span class="w">    </span><span class="nx">buf</span><span class="p">.</span><span class="nx">WriteByte</span><span class="p">(</span><span class="sc">&#39;{&#39;</span><span class="p">)</span><span class="w"></span>
<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="nx">i</span><span class="p">,</span><span class="w"> </span><span class="nx">word</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="k">range</span><span class="w"> </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="k">if</span><span class="w"> </span><span class="nx">word</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="k">continue</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"></span>
<span class="w">        </span><span class="k">for</span><span class="w"> </span><span class="nx">j</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="nx">j</span><span class="w"> </span><span class="p">&lt;</span><span class="w"> </span><span class="mi">64</span><span class="p">;</span><span class="w"> </span><span class="nx">j</span><span class="o">++</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="k">if</span><span class="w"> </span><span class="nx">word</span><span class="o">&amp;</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="nb">uint</span><span class="p">(</span><span class="nx">j</span><span class="p">))</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                </span><span class="k">if</span><span class="w"> </span><span class="nx">buf</span><span class="p">.</span><span class="nx">Len</span><span class="p">()</span><span class="w"> </span><span class="p">&gt;</span><span class="w"> </span><span class="nb">len</span><span class="p">(</span><span class="s">&quot;{&quot;</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                    </span><span class="nx">buf</span><span class="p">.</span><span class="nx">WriteByte</span><span class="p">(</span><span class="sc">&#39; &#39;</span><span class="p">)</span><span class="w"></span>
<span class="w">                </span><span class="p">}</span><span class="w"></span>
<span class="w">                </span><span class="nx">fmt</span><span class="p">.</span><span class="nx">Fprintf</span><span class="p">(</span><span class="o">&amp;</span><span class="nx">buf</span><span class="p">,</span><span class="w"> </span><span class="s">&quot;%d&quot;</span><span class="p">,</span><span class="w"> </span><span class="mi">64</span><span class="o">*</span><span class="nx">i</span><span class="o">+</span><span class="nx">j</span><span class="p">)</span><span class="w"></span>
<span class="w">            </span><span class="p">}</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="nx">buf</span><span class="p">.</span><span class="nx">WriteByte</span><span class="p">(</span><span class="sc">&#39;}&#39;</span><span class="p">)</span><span class="w"></span>
<span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="nx">buf</span><span class="p">.</span><span class="nx">String</span><span class="p">()</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>

<p>每一个 word 有64位，为了定位第 x 位的位置，通过 x/64 结果取整，就是 word 的索引，而 x%64 取模运算是 word 内位的索引。<br>
这里还自定义了以字符串输出 IntSet 的方法，就是一个 String 方法。在 String 方法中 bytes.Buffer 经常以这样的方式用到。<br>
因为 Add 方法和 UnionWith 方法需要对 s.word 进行赋值，所以需要用到指针。所以该类型的其他方法也都使用了指针，就是 Has 方法和 String 方法是不需要使用指针的，但是为了保持一致，就都使用指针作为方法的接收者。 </p>
<h4 id="bing-ji-jiao-ji-cha-ji-dui-chen-cha"><a class="toclink" href="#bing-ji-jiao-ji-cha-ji-dui-chen-cha">并集、交集、差集、对称差</a></h4>
<p>上面只给了并集的示例，这里提到的4种集合的计算，简单参考一下前面的“位运算符”的介绍，很简单的通过修改一下位运算的符号就能实现了。<br>
并集和对称差，需要把s.words中没有的而t.words中多的那些元素全部加进来。而交集和差集，直接无视这部分元素就好了：</p>
<div class="highlight"><pre><span></span><code><span class="c1">// 并集 Union，上面的示例中已经有了</span><span class="w"></span>
<span class="kd">func</span><span class="w"> </span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="nx">UnionWith</span><span class="p">(</span><span class="nx">t</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="nx">i</span><span class="p">,</span><span class="w"> </span><span class="nx">tword</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="k">range</span><span class="w"> </span><span class="nx">t</span><span class="p">.</span><span class="nx">words</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="k">if</span><span class="w"> </span><span class="nx">i</span><span class="w"> </span><span class="p">&lt;</span><span class="w"> </span><span class="nb">len</span><span class="p">(</span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="o">|=</span><span class="w"> </span><span class="nx">tword</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nb">append</span><span class="p">(</span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">,</span><span class="w"> </span><span class="nx">tword</span><span class="p">)</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="c1">// 交集 Intersection</span><span class="w"></span>
<span class="kd">func</span><span class="w"> </span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="nx">IntersectionWith</span><span class="p">(</span><span class="nx">t</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="nx">i</span><span class="p">,</span><span class="w"> </span><span class="nx">tword</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="k">range</span><span class="w"> </span><span class="nx">t</span><span class="p">.</span><span class="nx">words</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="k">if</span><span class="w"> </span><span class="nx">i</span><span class="w"> </span><span class="p">&lt;</span><span class="w"> </span><span class="nb">len</span><span class="p">(</span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="o">&amp;=</span><span class="w"> </span><span class="nx">tword</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="c1">// 差集 Difference</span><span class="w"></span>
<span class="kd">func</span><span class="w"> </span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="nx">DifferenceWith</span><span class="p">(</span><span class="nx">t</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="nx">i</span><span class="p">,</span><span class="w"> </span><span class="nx">tword</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="k">range</span><span class="w"> </span><span class="nx">t</span><span class="p">.</span><span class="nx">words</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="k">if</span><span class="w"> </span><span class="nx">i</span><span class="w"> </span><span class="p">&lt;</span><span class="w"> </span><span class="nb">len</span><span class="p">(</span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="o">&amp;^=</span><span class="w"> </span><span class="nx">tword</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="c1">// 对称差 SymmetricDifference</span><span class="w"></span>
<span class="kd">func</span><span class="w"> </span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="nx">SymmetricDifferenceWith</span><span class="p">(</span><span class="nx">t</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="nx">i</span><span class="p">,</span><span class="w"> </span><span class="nx">tword</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="k">range</span><span class="w"> </span><span class="nx">t</span><span class="p">.</span><span class="nx">words</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="k">if</span><span class="w"> </span><span class="nx">i</span><span class="w"> </span><span class="p">&lt;</span><span class="w"> </span><span class="nb">len</span><span class="p">(</span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="p">^=</span><span class="w"> </span><span class="nx">tword</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nb">append</span><span class="p">(</span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">,</span><span class="w"> </span><span class="nx">tword</span><span class="p">)</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>

<p>把这里的三个新的方法添加到最初定义的包中就可以使用。  </p>
<h4 id="ji-suan-zhi-wei-ge-shu"><a class="toclink" href="#ji-suan-zhi-wei-ge-shu">计算置位个数</a></h4>
<p>就是统计集合中元素的总数，下面分别讲3种实现的算法：</p>
<ol>
<li>查表法：空间换时间。</li>
<li>右移循环算法：最简单，最容易想到。</li>
<li>快速法：如果输入整数中“1”远小于“0”（稀疏）,可以通过一些针对性算法来提高效率。</li>
</ol>
<h5 id="cha-biao-fa"><a class="toclink" href="#cha-biao-fa">查表法</a></h5>
<p>先使用 init 函数来针对每一个可能的8位值预计算一个结果表 pc，这样之后只需要将每次快查表的结果相加而不用进行一步步的计算：</p>
<div class="highlight"><pre><span></span><code><span class="c1">// pc[i] 是 i 的 population count</span><span class="w"></span>
<span class="kd">var</span><span class="w"> </span><span class="nx">pc</span><span class="w"> </span><span class="p">[</span><span class="mi">256</span><span class="p">]</span><span class="kt">byte</span><span class="w"></span>

<span class="kd">func</span><span class="w"> </span><span class="nx">init</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="nx">i</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="k">range</span><span class="w"> </span><span class="nx">pc</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="nx">pc</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nx">pc</span><span class="p">[</span><span class="nx">i</span><span class="o">/</span><span class="mi">2</span><span class="p">]</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="nb">byte</span><span class="p">(</span><span class="nx">i</span><span class="o">&amp;</span><span class="mi">1</span><span class="p">)</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="c1">// 返回元素个数，查表法</span><span class="w"></span>
<span class="kd">func</span><span class="w"> </span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="nx">Len</span><span class="p">()</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="kd">var</span><span class="w"> </span><span class="nx">counts</span><span class="w"> </span><span class="kt">int</span><span class="w"></span>
<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="nx">_</span><span class="p">,</span><span class="w"> </span><span class="nx">word</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="k">range</span><span class="w"> </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="nx">counts</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="nb">int</span><span class="p">(</span><span class="nx">pc</span><span class="p">[</span><span class="nb">byte</span><span class="p">(</span><span class="nx">word</span><span class="o">&gt;&gt;</span><span class="p">(</span><span class="mi">0</span><span class="o">*</span><span class="mi">8</span><span class="p">))])</span><span class="w"></span>
<span class="w">        </span><span class="nx">counts</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="nb">int</span><span class="p">(</span><span class="nx">pc</span><span class="p">[</span><span class="nb">byte</span><span class="p">(</span><span class="nx">word</span><span class="o">&gt;&gt;</span><span class="p">(</span><span class="mi">1</span><span class="o">*</span><span class="mi">8</span><span class="p">))])</span><span class="w"></span>
<span class="w">        </span><span class="nx">counts</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="nb">int</span><span class="p">(</span><span class="nx">pc</span><span class="p">[</span><span class="nb">byte</span><span class="p">(</span><span class="nx">word</span><span class="o">&gt;&gt;</span><span class="p">(</span><span class="mi">2</span><span class="o">*</span><span class="mi">8</span><span class="p">))])</span><span class="w"></span>
<span class="w">        </span><span class="nx">counts</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="nb">int</span><span class="p">(</span><span class="nx">pc</span><span class="p">[</span><span class="nb">byte</span><span class="p">(</span><span class="nx">word</span><span class="o">&gt;&gt;</span><span class="p">(</span><span class="mi">3</span><span class="o">*</span><span class="mi">8</span><span class="p">))])</span><span class="w"></span>
<span class="w">        </span><span class="nx">counts</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="nb">int</span><span class="p">(</span><span class="nx">pc</span><span class="p">[</span><span class="nb">byte</span><span class="p">(</span><span class="nx">word</span><span class="o">&gt;&gt;</span><span class="p">(</span><span class="mi">4</span><span class="o">*</span><span class="mi">8</span><span class="p">))])</span><span class="w"></span>
<span class="w">        </span><span class="nx">counts</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="nb">int</span><span class="p">(</span><span class="nx">pc</span><span class="p">[</span><span class="nb">byte</span><span class="p">(</span><span class="nx">word</span><span class="o">&gt;&gt;</span><span class="p">(</span><span class="mi">5</span><span class="o">*</span><span class="mi">8</span><span class="p">))])</span><span class="w"></span>
<span class="w">        </span><span class="nx">counts</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="nb">int</span><span class="p">(</span><span class="nx">pc</span><span class="p">[</span><span class="nb">byte</span><span class="p">(</span><span class="nx">word</span><span class="o">&gt;&gt;</span><span class="p">(</span><span class="mi">6</span><span class="o">*</span><span class="mi">8</span><span class="p">))])</span><span class="w"></span>
<span class="w">        </span><span class="nx">counts</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="nb">int</span><span class="p">(</span><span class="nx">pc</span><span class="p">[</span><span class="nb">byte</span><span class="p">(</span><span class="nx">word</span><span class="o">&gt;&gt;</span><span class="p">(</span><span class="mi">7</span><span class="o">*</span><span class="mi">8</span><span class="p">))])</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="nx">counts</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>

<h5 id="you-yi-xun-huan-suan-fa"><a class="toclink" href="#you-yi-xun-huan-suan-fa">右移循环算法</a></h5>
<p>在其实际参数的位上执行移位操作，每次判断最右边的位，进而实现统计功能：</p>
<div class="highlight"><pre><span></span><code><span class="c1">// 返回元素个数，右移循环算法</span><span class="w"></span>
<span class="kd">func</span><span class="w"> </span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="nx">Len2</span><span class="p">()</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="kd">var</span><span class="w"> </span><span class="nx">count</span><span class="w"> </span><span class="kt">int</span><span class="w"></span>
<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="nx">_</span><span class="p">,</span><span class="w"> </span><span class="nx">x</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="k">range</span><span class="w"> </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="k">for</span><span class="w"> </span><span class="nx">x</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="k">if</span><span class="w"> </span><span class="nx">x</span><span class="w"> </span><span class="o">&amp;</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                </span><span class="nx">count</span><span class="o">++</span><span class="w"></span>
<span class="w">            </span><span class="p">}</span><span class="w"></span>
<span class="w">            </span><span class="nx">x</span><span class="w"> </span><span class="o">&gt;&gt;=</span><span class="w"> </span><span class="mi">1</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="nx">count</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>

<h5 id="kuai-su-fa"><a class="toclink" href="#kuai-su-fa">快速法</a></h5>
<p>使用 x&amp;(x-1) 可以清除x最右边的非零位，不停地进行这个运算直到数值变成0。其中进行了几次运行就表示有几个1了：</p>
<div class="highlight"><pre><span></span><code><span class="c1">// 返回元素个数，快速法</span><span class="w"></span>
<span class="kd">func</span><span class="w"> </span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="nx">Len3</span><span class="p">()</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="kd">var</span><span class="w"> </span><span class="nx">count</span><span class="w"> </span><span class="kt">int</span><span class="w"></span>
<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="nx">_</span><span class="p">,</span><span class="w"> </span><span class="nx">x</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="k">range</span><span class="w"> </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="k">for</span><span class="w"> </span><span class="nx">x</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="nx">x</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nx">x</span><span class="w"> </span><span class="o">&amp;</span><span class="w"> </span><span class="p">(</span><span class="nx">x</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">)</span><span class="w"></span>
<span class="w">            </span><span class="nx">count</span><span class="o">++</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="nx">count</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>

<h4 id="tian-jia-qi-ta-fang-fa"><a class="toclink" href="#tian-jia-qi-ta-fang-fa">添加其他方法</a></h4>
<p>继续为我们的位向量类型添加其他方法：</p>
<div class="highlight"><pre><span></span><code><span class="c1">// 一次添加多个元素</span><span class="w"></span>
<span class="kd">func</span><span class="w"> </span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="nx">AddAll</span><span class="p">(</span><span class="nx">nums</span><span class="w"> </span><span class="o">...</span><span class="kt">int</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="nx">_</span><span class="p">,</span><span class="w"> </span><span class="nx">x</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="k">range</span><span class="w"> </span><span class="nx">nums</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="nx">s</span><span class="p">.</span><span class="nx">Add</span><span class="p">(</span><span class="nx">x</span><span class="p">)</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="c1">// 移除元素，无论是否在集合中，都把该位置置0</span><span class="w"></span>
<span class="kd">func</span><span class="w"> </span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="nx">Remove</span><span class="p">(</span><span class="nx">x</span><span class="w"> </span><span class="kt">int</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="nx">word</span><span class="p">,</span><span class="w"> </span><span class="nx">bit</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">x</span><span class="o">/</span><span class="nx">bitCounts</span><span class="p">,</span><span class="w"> </span><span class="nb">uint</span><span class="p">(</span><span class="nx">x</span><span class="o">%</span><span class="nx">bitCounts</span><span class="p">)</span><span class="w"></span>
<span class="w">    </span><span class="k">if</span><span class="w"> </span><span class="nx">word</span><span class="w"> </span><span class="p">&lt;</span><span class="w"> </span><span class="nb">len</span><span class="p">(</span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">[</span><span class="nx">word</span><span class="p">]</span><span class="w"> </span><span class="o">&amp;^=</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="o">&lt;&lt;</span><span class="w"> </span><span class="nx">bit</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="c1">// 移除高位全零的元素</span><span class="w"></span>
<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="nx">i</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nb">len</span><span class="p">(</span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">)</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span><span class="w"> </span><span class="nx">i</span><span class="w"> </span><span class="o">&gt;=</span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="nx">i</span><span class="o">--</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="k">if</span><span class="w"> </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">[:</span><span class="nx">i</span><span class="p">]</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="k">break</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="c1">// 删除所有元素</span><span class="w"></span>
<span class="kd">func</span><span class="w"> </span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="nx">Clear</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="o">*</span><span class="nx">s</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nx">IntSet</span><span class="p">{}</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="c1">// 返回集合的副本</span><span class="w"></span>
<span class="kd">func</span><span class="w"> </span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="nx">Copy</span><span class="p">()</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="nx">x</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">IntSet</span><span class="p">{</span><span class="nx">words</span><span class="p">:</span><span class="w"> </span><span class="nb">make</span><span class="p">([]</span><span class="kt">uint</span><span class="p">,</span><span class="w"> </span><span class="nb">len</span><span class="p">(</span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">))}</span><span class="w"></span>
<span class="w">    </span><span class="nb">copy</span><span class="p">(</span><span class="nx">x</span><span class="p">.</span><span class="nx">words</span><span class="p">,</span><span class="w"> </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">)</span><span class="w"></span>
<span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="o">&amp;</span><span class="nx">x</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="c1">// 返回包含集合元素的 slice，这适合在 range 循环中使用</span><span class="w"></span>
<span class="kd">func</span><span class="w"> </span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="nx">Elems</span><span class="p">()</span><span class="w"> </span><span class="p">[]</span><span class="kt">int</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="kd">var</span><span class="w"> </span><span class="nx">ret</span><span class="w"> </span><span class="p">[]</span><span class="kt">int</span><span class="w"></span>
<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="nx">i</span><span class="p">,</span><span class="w"> </span><span class="nx">word</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="k">range</span><span class="w"> </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="k">if</span><span class="w"> </span><span class="nx">word</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="k">continue</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"></span>
<span class="w">        </span><span class="k">for</span><span class="w"> </span><span class="nx">j</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="nx">j</span><span class="w"> </span><span class="p">&lt;</span><span class="w"> </span><span class="nx">bitCounts</span><span class="p">;</span><span class="w"> </span><span class="nx">j</span><span class="o">++</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="k">if</span><span class="w"> </span><span class="nx">word</span><span class="o">&amp;</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="nb">uint</span><span class="p">(</span><span class="nx">j</span><span class="p">))</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                </span><span class="nx">ret</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nb">append</span><span class="p">(</span><span class="nx">ret</span><span class="p">,</span><span class="w"> </span><span class="nx">bitCounts</span><span class="o">*</span><span class="nx">i</span><span class="o">+</span><span class="nx">j</span><span class="p">)</span><span class="w"></span>
<span class="w">            </span><span class="p">}</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="nx">ret</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>

<h4 id="zi-shi-ying-32-huo-64-wei-ping-tai"><a class="toclink" href="#zi-shi-ying-32-huo-64-wei-ping-tai">自适应32或64位平台</a></h4>
<p>这里每个字的类型都是 uint64，但是64位的计算在32位的平台上的效率不高。使用 uint 类型，这是适合平台的无符号整型。除以64的操作可以使用一个常量来代表32位或64位。<br>
这里有一个讨巧的表达式： 32&lt;&lt;(^uint(0)&gt;&gt;63) 。在不同的平台上计算的结果就是32或64。</p>
<div class="highlight"><pre><span></span><code><span class="kd">const</span><span class="w"> </span><span class="nx">bitCounts</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">32</span><span class="w"> </span><span class="o">&lt;&lt;</span><span class="w"> </span><span class="p">(^</span><span class="nb">uint</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span><span class="w"> </span><span class="o">&gt;&gt;</span><span class="w"> </span><span class="mi">63</span><span class="p">)</span><span class="w"> </span><span class="c1">// 使用这个常量去做取模和取余的计算</span><span class="w"></span>
</code></pre></div>

<p>对应的要把代码中原本直接使用数字常量64的地方替换成这个常量，比如 Has 方法：</p>
<div class="highlight"><pre><span></span><code><span class="kd">const</span><span class="w"> </span><span class="nx">bitCounts</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">32</span><span class="w"> </span><span class="o">&lt;&lt;</span><span class="w"> </span><span class="p">(^</span><span class="nb">uint</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span><span class="w"> </span><span class="o">&gt;&gt;</span><span class="w"> </span><span class="mi">63</span><span class="p">)</span><span class="w"> </span><span class="c1">// 32位平台这个值就是32，64位平台这个值就是64</span><span class="w"></span>

<span class="c1">// 集合中是否存在非负整数x</span><span class="w"></span>
<span class="kd">func</span><span class="w"> </span><span class="p">(</span><span class="nx">s</span><span class="w"> </span><span class="o">*</span><span class="nx">IntSet</span><span class="p">)</span><span class="w"> </span><span class="nx">Has</span><span class="p">(</span><span class="nx">x</span><span class="w"> </span><span class="kt">int</span><span class="p">)</span><span class="w"> </span><span class="kt">bool</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="nx">word</span><span class="p">,</span><span class="w"> </span><span class="nx">bit</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">x</span><span class="o">/</span><span class="nx">bitCounts</span><span class="p">,</span><span class="w"> </span><span class="nb">uint</span><span class="p">(</span><span class="nx">x</span><span class="o">%</span><span class="nx">bitCounts</span><span class="p">)</span><span class="w"></span>
<span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="nx">word</span><span class="w"> </span><span class="p">&lt;</span><span class="w"> </span><span class="nb">len</span><span class="p">(</span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">)</span><span class="w"> </span><span class="o">&amp;&amp;</span><span class="w"> </span><span class="nx">s</span><span class="p">.</span><span class="nx">words</span><span class="p">[</span><span class="nx">word</span><span class="p">]</span><span class="o">&amp;</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="nx">bit</span><span class="p">)</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="mi">0</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>
      </div>
      <div class="back-to-top">
        <a href="/">HOME</a>
        <a href="#top">TOP</a>
      </div>
    </article>
  </div>
<!-- end article -->
<!-- 页面往下滚动一段之后才会显示TOC -->
<script>
  window.onscroll = function() {
    var tocbox = document.getElementsByClassName('toc')[0];
    var osTop = document.documentElement.scrollTop || document.body.scrollTop;
    var osWidth = document.documentElement.scrollWidth || document.body.scrollWidth;
    // console.log(osTop)
    if (osTop>300 && osWidth>865) {
      tocbox.style.display = "block"
    }
    if (osTop<300 || osWidth<865) {
      tocbox.style.display = "none"
    }
  }
</script>
                <footer>
                    <div class="icons">
                    </div>
                    <span id="busuanzi_container_page_pv" style="padding: 10px">本文阅读量<span id="busuanzi_value_page_pv"></span>次</span>
                    <span id="busuanzi_container_site_pv" style="padding: 10px">本站总访问量<span id="busuanzi_value_site_pv"></span>次</span>
                    <span id="busuanzi_container_site_uv" style="padding: 10px">本站总访客数<span id="busuanzi_value_site_uv"></span>人</span>
                    <p>© <script>document.write(moment().format('YYYY'));</script> 749B</p>
                </footer>
        </div>
</body>
</html>